#include <iostream>
int EuclidAlgorithm(int a, int b){
if(b==0) return a;
else return EuclidAlgorithm(b, a%b);
}
struct int3{
int a, b, c;
int3(int _a, int _b, int _c=0): a(_a), b(_b), c(_c) {}
};
int3 ExtendedEuclid(int a, int b){
if(b==0) return int3(a, 1, 0);
else {
int3 dxy=ExtendedEuclid(b, a%b);
int3 output(dxy.a, dxy.c, dxy.b-(a/b)*dxy.c);
return output;
}
}
int main(void){
int a=99, b=78;
int c=EuclidAlgorithm(a, b);
std::cout<<"GCD( "<<a<<", "<<b<<" ) = "<<c<<std::endl;
int3 input(a, b, 0);
int3 output=ExtendedEuclid(a, b);
std::cout<<output.a<<" : "<<output.b<<" : "<<output.c<<std::endl;
return 0;
}